% Автор: Сергей Копелиович
% Источник: CS-Center, осень 2013-2014

\begin{problem}{Числа Каталана}
{catalan.in}{catalan.out}
{1 секунда}{256 мегабайт}{}

Числа Каталана определяются следущим образом:

1. $C_0 = 1$

2. $C_n = \sum\limits_{i=0}^{n-1}C_iC_{n-i-1}$

Ваша задача --- посчитать $C_n \mod m$.

\InputFile

На первой строке целые числа $n$ ($0 \le n \le 1000$) и $m$ ($1 \le m \le 10^9$).

\OutputFile

Выведите одно целое число --- $C_n \mod m$.

\Examples

\begin{example}
\exmp{
5 1000000000
}{
42
}%
\end{example}

\end{problem}
